{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Unitary Patterns\n",
    "\n",
    "The **\"Unitary Patterns\"** quantum kata is a series of exercises designed\n",
    "to get you comfortable with creating unitary transformations which can be represented\n",
    "with matrices of certain shapes (with certain pattern of zero and non-zero values).\n",
    "\n",
    "Each task is wrapped in one operation preceded by the description of the task.\n",
    "Your goal is to fill in the blank (marked with the `// ...` comments)\n",
    "with some Q# code that solves the task. To verify your answer, run the cell using Ctrl+Enter (⌘+Enter on macOS).\n",
    "\n",
    "Within each section, tasks are given in approximate order of increasing difficulty; \n",
    "harder ones are marked with asterisks.\n",
    "\n",
    "<br/>\n",
    "\n",
    "Each task describes a matrix which your unitary needs to implement.\n",
    "The row and column indices of the matrix elements are in little-endian format (the least significant bit is stored first).\n",
    "For example, index 1 corresponds to the qubit state $|10...0\\rangle$, and to store this state in an array of qubits `qs` \n",
    "its first element `qs[0]` would have to be in state $|1\\rangle$ and the rest of the qubits would have to be in state $|0\\rangle$.\n",
    "\n",
    "In the example patterns provided in the tasks, `X` marks a \"non-zero\" element, and `.` marks a \"zero\" element.\n",
    "A \"zero\" element of a matrix is a complex number which has an absolute value of 0.001 or less,\n",
    "and a \"non-zero\" element is a complex number which has an absolute value of 0.001 or greater.\n",
    "You can see the details of the verification in [`Tests.qs`](.\\Tests.qs) file, operation `AssertOperationMatrixMatchesPattern`.\n",
    "\n",
    "Note that all tasks require you to implement a unitary transformation,\n",
    "which means that you're not allowed to use any measurements."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1. Main diagonal\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:** \n",
    "Implement a unitary transformation on N qubits which is represented by a matrix\n",
    "with non-zero elements on the main diagonal and zero elements everywhere else.\n",
    "\n",
    "**Example:** For N = 2, the matrix of the transformation should look as follows:\n",
    "\n",
    "    X...\n",
    "    .X..\n",
    "    ..X.\n",
    "    ...X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T01_MainDiagonal \n",
    "\n",
    "operation MainDiagonal (qs : Qubit[]) : Unit {\n",
    "    // The simplest example of such a unitary transformation is represented by an identity matrix.\n",
    "    // This means that the operation doesn't need to do anything with the input qubits.\n",
    "    // Execute this cell to see that this solution is correct.\n",
    "\n",
    "    // You are welcome to try and come up with other diagonal unitaries.\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Unitary Patterns Workbook](./Workbook_UnitaryPatterns.ipynb#Task-1.-Main-diagonal).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2. All-non-zero matrix\n",
    "\n",
    "**Input:**\n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:** \n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "with all elements non-zero.\n",
    "\n",
    "**Example:** For N = 2, the matrix of the transformation should look as follows:\n",
    "\n",
    "    XXXX\n",
    "    XXXX\n",
    "    XXXX\n",
    "    XXXX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T02_AllNonZero \n",
    "\n",
    "operation AllNonZero (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Unitary Patterns Workbook](./Workbook_UnitaryPatterns.ipynb#Task-2.-All-non-zero-matrix).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3. Block diagonal matrix\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:** \n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "which has $2 \\times 2$ blocks of non-zero elements on the main diagonal and zero elements everywhere else.\n",
    "\n",
    "**Example:** \n",
    "For N = 3, the matrix of the transformation should look as follows:\n",
    "\n",
    "    XX......\n",
    "    XX......\n",
    "    ..XX....\n",
    "    ..XX....\n",
    "    ....XX..\n",
    "    ....XX..\n",
    "    ......XX\n",
    "    ......XX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T03_BlockDiagonal \n",
    "\n",
    "operation BlockDiagonal (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Unitary Patterns Workbook](./Workbook_UnitaryPatterns.ipynb#Task-3.-Block-diagonal-matrix).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 4. Quarters\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "with non-zero elements in top left and bottom right quarters \n",
    "and zero elements everywhere else.\n",
    "\n",
    "**Example:** \n",
    "For N = 3, the matrix of the transformation should look as follows:\n",
    "\n",
    "    XXXX....\n",
    "    XXXX....\n",
    "    XXXX....\n",
    "    XXXX....\n",
    "    ....XXXX\n",
    "    ....XXXX\n",
    "    ....XXXX\n",
    "    ....XXXX\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  Represent this matrix as a tensor product of a $2 \\times 2$ diagonal matrix and a larger matrix with all non-zero elements.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T04_Quarters \n",
    "\n",
    "operation Quarters (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Unitary Patterns Workbook](./Workbook_UnitaryPatterns.ipynb#Task-4.-Quarters).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 5. Even chessboard pattern\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "with non-zero elements in positions where row and column indices have the same parity \n",
    "and zero elements everywhere else.\n",
    "\n",
    "**Example:** \n",
    "For N = 2, the matrix of the transformation should look as follows:\n",
    "\n",
    "    X.X.\n",
    "    .X.X\n",
    "    X.X.\n",
    "    .X.X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T05_EvenChessPattern \n",
    "\n",
    "operation EvenChessPattern (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Unitary Patterns Workbook](./Workbook_UnitaryPatterns.ipynb#Task-5.-Even-chessboard-pattern).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 6. Odd chessboard pattern\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "with non-zero elements in positions where row and column indices have different parity \n",
    "and zero elements everywhere else.\n",
    "\n",
    "**Example:** \n",
    "For N = 2, the matrix of the transformation should look as follows:\n",
    "\n",
    "    .X.X\n",
    "    X.X.\n",
    "    .X.X\n",
    "    X.X."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T06_OddChessPattern \n",
    "\n",
    "operation OddChessPattern (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Unitary Patterns Workbook](./Workbook_UnitaryPatterns.ipynb#Task-6.-Odd-chessboard-pattern).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 7. Anti-diagonal\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "with non-zero elements on the anti-diagonal and zero elements everywhere else.\n",
    "\n",
    "**Example:** \n",
    "For N = 2, the matrix of the transformation should look as follows:\n",
    "\n",
    "    ...X\n",
    "    ..X.\n",
    "    .X..\n",
    "    X..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T07_Antidiagonal \n",
    "\n",
    "operation Antidiagonal (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Unitary Patterns Workbook](./Workbook_UnitaryPatterns.ipynb#Task-7.-Anti-diagonal).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 8. 2 x 2 chessboard pattern\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "in which zero and non-zero elements form a chessboard pattern with 2x2 squares, \n",
    "with the top left square occupied by non-zero elements.\n",
    "\n",
    "**Example:** \n",
    "For N = 3, the matrix of the transformation should look as follows:\n",
    "\n",
    "    XX..XX..\n",
    "    XX..XX..\n",
    "    ..XX..XX\n",
    "    ..XX..XX\n",
    "    XX..XX..\n",
    "    XX..XX..\n",
    "    ..XX..XX\n",
    "    ..XX..XX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T08_ChessPattern2x2 \n",
    "\n",
    "operation ChessPattern2x2 (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Unitary Patterns Workbook](./Workbook_UnitaryPatterns.ipynb#Task-8.-2-x-2-chessboard-pattern).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 9. Two patterns\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix with \n",
    "* all zero elements in the top right and bottom left quarters, \n",
    "* an anti-diagonal pattern from task 7 in the top left quarter, \n",
    "* and an all-non-zero pattern from task 2 in the bottom right quarter.\n",
    "\n",
    "**Example:** \n",
    "For N = 2, the matrix of the transformation should look as follows:\n",
    "\n",
    "    .X..\n",
    "    X...\n",
    "    ..XX\n",
    "    ..XX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T09_TwoPatterns \n",
    "\n",
    "operation TwoPatterns (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Unitary Patterns Workbook](./Workbook_UnitaryPatterns.ipynb#Task-9.-Two-patterns).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 10. Increasing blocks\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix defined recursively:\n",
    "\n",
    "* For N = 1 the matrix has non-zero elements on the main diagonal and zero elements everywhere else,\n",
    "* For larger N the matrix has\n",
    "   * all zero elements in the top right and bottom left quarters,\n",
    "   * the matrix for N-1 in the top left quarter, and \n",
    "   * all non-zero elements in the bottom right quarter.\n",
    "\n",
    "**Example:** \n",
    "For N = 3, the matrix of the transformation should look as follows:\n",
    "\n",
    "    X.......\n",
    "    .X......\n",
    "    ..XX....\n",
    "    ..XX....\n",
    "    ....XXXX\n",
    "    ....XXXX\n",
    "    ....XXXX\n",
    "    ....XXXX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T10_IncreasingBlocks \n",
    "\n",
    "operation IncreasingBlocks (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Unitary Patterns Workbook](./Workbook_UnitaryPatterns.ipynb#Task-10.-Increasing-blocks).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 11. X-Wing fighter\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "with non-zero elements on the main diagonal and the anti-diagonal \n",
    "and zero elements everywhere else.\n",
    "\n",
    "**Example:** \n",
    "For N = 3, the matrix of the transformation should look as follows:\n",
    "\n",
    "    X......X\n",
    "    .X....X.\n",
    "    ..X..X..\n",
    "    ...XX...\n",
    "    ...XX...\n",
    "    ..X..X..\n",
    "    .X....X.\n",
    "    X......X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_XWing_Fighter \n",
    "\n",
    "operation XWing_Fighter (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Unitary Patterns Workbook](./Workbook_UnitaryPatterns.ipynb#Task-11.-X-Wing-fighter).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 12. Rhombus\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "with non-zero elements forming a rhombus of width 1 with sides parallel to main diagonals.\n",
    "\n",
    "**Example:** \n",
    "For N = 2, the matrix of the transformation should look as follows:\n",
    "\n",
    "    .XX.\n",
    "    X..X\n",
    "    X..X\n",
    "    .XX.\n",
    "\n",
    "For N = 3, the matrix of the transformation should look as follows:\n",
    "\n",
    "    ...XX...\n",
    "    ..X..X..\n",
    "    .X....X.\n",
    "    X......X\n",
    "    X......X\n",
    "    .X....X.\n",
    "    ..X..X..\n",
    "    ...XX..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T12_Rhombus \n",
    "\n",
    "operation Rhombus (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Unitary Patterns Workbook](./Workbook_UnitaryPatterns.ipynb#Task-12.-Rhombus).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 13**. TIE fighter\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state ($2 \\leq N \\leq 5$).\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "with non-zero elements in the following positions:\n",
    "\n",
    "- The central $2 \\times 2$ sub-matrix;\n",
    "\n",
    "- The diagonals of the top right and bottom left sub-matrices of size $2^{N-1}-1$\n",
    "that do not overlap with the central $2 \\times 2$ sub-matrix;\n",
    "\n",
    "- The anti-diagonals of the top left and bottom right sub-matrices of size $2^{N-1}-1$\n",
    "that do not overlap with the central $2 \\times 2$ sub-matrix.\n",
    "\n",
    "**Example:** \n",
    "\n",
    "For N = 3, the matrix of the transformation should look as follows:\n",
    "\n",
    "    ..X..X..\n",
    "    .X....X.\n",
    "    X......X\n",
    "    ...XX...\n",
    "    ...XX...\n",
    "    X......X\n",
    "    .X....X.\n",
    "    ..X..X.."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T13_TIE_Fighter \n",
    "\n",
    "operation TIE_Fighter (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Unitary Patterns Workbook](./Workbook_UnitaryPatterns.ipynb#Task-13**.-TIE-fighter).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 14**. Creeper\n",
    "\n",
    "**Input:** \n",
    "3 qubits in an arbitrary state.\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on 3 qubits which is represented by a matrix \n",
    "with non-zero elements in the following pattern: \n",
    "\n",
    "    XX....XX\n",
    "    XX....XX\n",
    "    ...XX...\n",
    "    ...XX...\n",
    "    ..X..X..\n",
    "    ..X..X..\n",
    "    XX....XX\n",
    "    XX....XX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T14_Creeper \n",
    "\n",
    "operation Creeper (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Unitary Patterns Workbook](./Workbook_UnitaryPatterns.ipynb#Task-14**.-Creeper).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 15**. Hessenberg matrices\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state ($2 \\leq N \\leq 4$).\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "with non-zero elements forming an upper diagonal matrix plus the first subdiagonal. \n",
    "This is called a [Hessenberg matrix](https://en.wikipedia.org/wiki/Hessenberg_matrix).\n",
    "\n",
    "**Example:** \n",
    "For N = 2, the matrix of the transformation should look as follows:\n",
    "\n",
    "    XXXX\n",
    "    XXXX\n",
    "    .XXX\n",
    "    ..XX\n",
    "\n",
    "For N = 3, the matrix of the transformation should look as follows:\n",
    "\n",
    "    XXXXXXXX\n",
    "    XXXXXXXX\n",
    "    .XXXXXXX\n",
    "    ..XXXXXX\n",
    "    ...XXXXX\n",
    "    ....XXXX\n",
    "    .....XXX\n",
    "    ......XX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T15_Hessenberg_Matrix \n",
    "\n",
    "operation Hessenberg_Matrix (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Unitary Patterns Workbook](./Workbook_UnitaryPatterns.ipynb#Task-15**.-Hessenberg-matrices).*"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Raw Cell Format",
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
